1. Field of The Invention
The present invention relates generally to computer graphics and animation systems and, more particularly, to geometry accelerators that perform clipping operations in a computer graphics and animation system.
2. Related Art
Computer graphics systems are commonly used for displaying two- and three-dimensional graphical representations of objects on a two-dimensional video display screen. Current computer graphics systems provide highly detailed representations and are used in a variety of applications.
In a typical computer graphics system an object or model to be represented on the display screen is broken down into a plurality of graphics primitives. Primitives are basic components of a graphics display and may include, for example, points, lines, vectors, and polygons such as triangles and quadrilaterals. Typically, a hardware/software scheme is implemented to render, or draw, the graphics primitives that represent a view of one or more objects being represented on the display screen.
Generally, the primitives of the three-dimensional object to be rendered are defined by a host computer in terms of primitive data. For example, when the primitive is a triangle, the host computer may define the primitives in terms of the coordinates (X, Y, Z, and W) of its vertices, as well as the red, green and blue and alpha (R, G, B and .alpha.) color values of each vertex. Additional primitive data may be used in specific applications. Rendering hardware interpolates the primitive data to compute the display screen pixels that represent each primitive, and the R, G, and B color values for each pixel.
The basic components of a computer graphics system typically include a geometry accelerator, a rasterizer, and a frame buffer. The system may also include other hardware such as texture mapping hardware. The geometry accelerator receives primitive data from the host computer that defines the primitives that make up the model view to be displayed. The geometry accelerator performs transformations on the primitive data and may also perform such functions as lighting, clipping, and plane equation calculations for each primitive. The output of the geometry accelerator, referred to as rendering data, is used by the rasterizer and the texture mapping hardware to generate final screen coordinate and color data for each pixel in each primitive. The pixel data from the rasterizer and the pixel data from the texture mapping hardware, if available, are combined and stored in the frame buffer for display on the video display screen.
One of the more complex operations that may be performed by a geometry accelerator is the clipping of graphics primitives. Clipping determines what portion of a graphics primitive is to be displayed in what is known as a "clip region." The clip region can be a two-dimensional area such as a window, or it can be a three-dimensional view volume. The primitives that are displayed in the clip region can be one-dimensional primitives (e.g., points or lines) or two-dimensional primitives (e.g., polygons).
The clipping of graphics primitives to a three-dimensional view volume is termed "view clipping". The three-dimensional view volume is defined by 6 orthogonal clipping planes, for example, Xmax, Xmin, Ymax, Ymin, Zmax, Zmin. View clipping of primitives is required due to the finite size of the video display, but may also be required by downstream hardware rasterizers to prevent overflow of the rasterizer's internal counters. View clipping can also be used to increase performance of the graphics system, as further processing on primitives that lie outside the view volume need not be performed. In addition to performing view clipping, many graphics systems also perform "model clipping" of graphics primitives. Model clipping allows a user to specify one or more model clipping planes that may be used to further restrict the viewing volume or to remove portions of an object or model from view. The commonly available OpenGL.RTM. graphics interface requires the graphics systems to support at least 6 model clipping planes. Accordingly, many graphics systems support 6 or more model clipping planes. By removing certain portions of the object or model from view, other areas of the model that were previously hidden from view can be visualized. (OpenGL is a registered trademark of Silicon Graphics, Inc.).
Various techniques have been developed for clipping points, lines, and polygons. Some of these are: Cohen-Sutherland line clipping, parametric line clipping, Weiler polygon clipping, Liang-Barsky polygon clipping, and Sutherland-Hodgman polygon clipping. Of the various techniques for clipping polygons, the Sutherland-Hodgman polygon clipping technique is perhaps the most widely used and generally applicable technique for clipping an input polygon against an arbitrary number of clipping planes. The Sutherland-Hodgman technique can be used to clip an input polygon against an arbitrary number of clipping planes by using the output from a first clip as the input to the next clip, until all clipping planes have been processed. For example, to clip an input polygon against the six orthogonal planes defining a view volume, the Sutherland-Hodgman technique clips each edge of the input polygon (as defined by the vertices of the input polygon) against a first clipping plane of the view volume to generate a first set of output vertices. Each edge of the output polygon defined by the first set of output vertices is then clipped against a second clipping plane of the view volume to generate a second set of output vertices. The resulting polygon defined by the second set of output vertices is then clipped against a third clipping plane and so on, until all of the clipping planes defining the view volume have been processed. The set of output vertices from the last clip then define a geometrically-shaped primitive (simple referred to as a "geometry" herein) that is bounded by the 6 orthogonal clipping planes of the view volume. The other polygon clipping techniques perform similar operations of successively clipping an input polygon against each plane of an arbitrary number of clipping planes.
Each of these conventional clipping techniques involves computationally intensive graphical manipulations, particularly when clipping polygons against a three dimensional clip region, such as a view volume. Although the clipping of graphics primitives may be performed within the geometry accelerator by means of a hardware-based clipping machine, it is frequently performed by the graphics system in software, or in a combination of both software and hardware. For example, the clipping of simple graphics primitives, such as points and lines, is straight-forward and well known in the art, and may be performed by dedicated hardware within the geometry accelerator. However, the clipping of more complex graphics primitives, such as triangles and other polygons, is more complex, and is conventionally performed by software. One reason for performing clipping of complex graphics primitives in software rather than in hardware within the geometry accelerator is that this is where such clipping has been historically performed. Another reason is that hardware implementations are generally more expensive, in terms of development and test time, cost, and risk, than software implementations. As a result, the benefits involved in placing such functionality in hardware clearly did not outweigh the benefits associated with software implementations, particularly since the clipping of graphics primitives is generally performed rarely by the geometry accelerator.
A further reason for performing clipping of more complex graphics primitives in software rather than hardware is due to the amount of hardware that is needed to perform the clipping operations. In particular, in addition to the hardware needed to perform the actual clipping of more complex graphics primitives, such as triangles or polygons, a substantial amount of memory is also needed to store vertex data. For example, each vertex of a graphic primitive may contain up to sixteen 32 bit words (e.g., spatial coordinate data X, Y, Z, and W, color coordinate data R, G, B, and a, and texture data SR, SG, SB, TS, TT, TR, TQ, D). Each time that a complex primitive, for example a triangle, is intersected by a clipping plane, a new vertex can be created. Thus, if the geometry accelerator supports back-to-back view clipping on 6 view clipping planes and model clipping on up to 6 user defined model clipping planes in a conventional manner, then the memory needs to be able to store at least 15 vertices; the 12 potential new vertices, and the original 3 vertices of the triangle.
However, this amount of memory consumes a large amount of surface area within a geometry accelerator. Providing this amount of memory dedicated to storing vertex data for clipping generally requires sacrificing some other function. Although memory dedicated to storing vertex data for clipping does not need to be located within the geometry accelerator, locating this memory elsewhere decreases the speed and efficiency by which clipping is performed. Moreover, the clipping of complex graphics primitives is only a subset of those functions that a geometry accelerator may perform, and such clipping frequently does not need to be performed at all. Accordingly, for each of the above reasons, the clipping of more complex graphics primitives is conventionally performed in software by the graphics system, rather than in hardware within a geometry accelerator.